As the use of the Internet and the World Wide Web (“Web”) has become widespread, it is increasingly common for users to access and use various types of capabilities provided by remote computing systems over the Web, including to search for, shop for and order items (such as products, services and/or information) that are for purchase, rent, lease, license, trade, evaluation, sampling, subscription to, etc. In addition to such user-initiated interactions, software programs on remote computing systems may also interact for various purposes and in various ways. For example, there is growing use of the Web to provide so-called “Web services,” which typically involve the programmatic interaction of remote applications to exchange information via defined APIs (“application program interfaces”). Web services allow heterogeneous applications and computers to interact, and may be defined and implemented using a variety of underlying protocols and techniques. For example, some Web service implementations return data in XML (“eXtensible Markup Language”) format using HTTP (“HyperText Transport Protocol”) in response to a Web service invocation request specified as a URI (“Uniform Resource Identifier”), such as a URL (“Uniform Resource Locator”) that includes a specified operation and one or more query parameters. Such URI-based invocation requests may, for example, be based on the use of XML over HTTP (e.g., as part of the REpresentational State Transfer, or “REST”, distributed interaction model that focuses on resources). In other implementations, additional underlying protocols are used for various purposes, such as SOAP (“Simple Object Access Protocol”) for standard message exchange, WSDL (“Web Services Description Language”) for description of service invocations, and UDDI (“Universal Description, Discovery, and Integration service”) for discovery of available services.
While capabilities provided by services over networks to remote users and other clients have various benefits, various problems also exist. For example, as the scale of such offerings increases (e.g., to support large numbers of clients), large numbers of computing devices may become available throughout the world to store data related to the clients and/or to handle requests from and other interactions with the clients. However, among other potential issues, it can be difficult to manage the storage of data and to coordinate the various computing devices in such situations in order to provide desired behavior.